package gold.digger;

import java.util.*;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC123 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int maxProfit(int[] prices) {
            if (prices == null || prices.length == 0) {
                return 0;
            }
            int n = prices.length;
            //用一个哈希表缓存重复的调用
            Map<Key, Integer> map = new HashMap<Key, Integer>();
            return dfs(map, prices, 0, 0, 0);
        }

        private int dfs(Map<Key, Integer> map, int[] prices, int index, int status, int k) {
            Key key = new Key(index, status, k);
            if (map.containsKey(key)) {
                return map.get(key);
            }
            if (index == prices.length || k == 2) {
                return 0;
            }
            int a = 0, b = 0, c = 0;
            a = dfs(map, prices, index + 1, status, k);
            if (status == 1) {
                b = dfs(map, prices, index + 1, 0, k + 1) + prices[index];
            } else {
                c = dfs(map, prices, index + 1, 1, k) - prices[index];
            }
            map.put(key, Math.max(Math.max(a, b), c));
            return map.get(key);
        }

        //Key对象封装了index、status、交易次数，作为map的key
        private class Key {
            final int index;
            final int status;
            final int k;

            Key(int index, int status, int k) {
                this.index = index;
                this.status = status;
                this.k = k;
            }

            //这里需要实现自定义的equals和hashCode函数
            public int hashCode() {
                return this.index + this.status + this.k;
            }

            public boolean equals(Object obj) {
                Key other = (Key) obj;
                if (index == other.index && status == other.status && k == other.k) {
                    return true;
                }
                return false;
            }
        }
    }


    public void run() {
        Solution solution = new Solution();
        List<Integer> list = new ArrayList<>();
        System.out.println(solution.toString());
    }

    public static void main(String[] args) throws Exception {
        LC123 an = new LC123();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
